﻿#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"state.h"

void select(HuffmanTree *HT, int c,int *a,int *b){
	int i=0, min1=1000, min2=1001,s1=10000,s2;
	while(i != c) {
		if(HT->head[i].parent != -1) {
			i++;
			continue;
		}
		if(HT->head[i].weight < min1){
			min2=min1;
			s2=s1;
			min1=HT->head[i].weight;
			s1=i;
		}else if(HT->head[i].weight<min2){
			min2=HT->head[i].weight;
			s2=i;
		}
		i++;
	}
	*a = s1;
	*b = s2;
}
/*
 * Huffman()
 * USAGE : generating Huffman codes
 * HT : BST save in it
 * w : weight of each element
 * n : number of nodes
 */
char ** HuffmanCoding(HuffmanTree *HT, int *w, int n){
	int m,i, s1,s2, f, c ,start;
	char *cd, ** HC;
	HTNode *p;
	if(n<=1) return;
	m = 2 * n - 1;
	HT->head=(HTNode *)malloc((m)*sizeof(HTNode));
	for(p = HT->head, i=0; i<n; ++i, ++p, ++w)	{p->weight = *w; p->lchild=-1;p->rchild=-1;p->parent=-1;}
	for(; i<m; ++i, ++p)	{p->weight = -1; p->lchild=-1;p->rchild=-1;p->parent=-1;}
	for(i = n; i<m; ++i){
		select(HT,i , &s1, &s2);
		HT->head[s1].parent = i; HT->head[s2].parent = i;
		HT->head[i].lchild = s1; HT->head[i].rchild = s2;
		HT->head[i].weight = HT->head[s1].weight + HT->head[s2].weight;
	}
	HC = (char **)malloc((n+1) * sizeof(char *));
	cd = (char*) malloc(n*sizeof(char));
	cd[n-1] = '\0';
	cd[n-2]='1';
	for(i=0; i<n; ++i){
		start = n-1;
		for(c = i, f=HT->head[i].parent; f != -1; c = f, f = HT->head[f].parent)
			if(HT->head[f].lchild == c)	cd[--start] = '0';
			else cd[--start] = '1';
		HC[i] = (char *) malloc((n-start)*sizeof(char));
		strcpy(HC[i], &cd[start]);
	}
	free(cd);
	return HC;
}
/*
 * count()
 * USAGE : return number of each char
 * a : string
 * n : length of a
 * b : charset
 * m : size of charset
 */
int * count(char *a,int n,int m,char b[]){
	int i,j;
	int *c;
	c= (int *)malloc(m*sizeof(int));
	for(i=0;i<m;i++)	c[i]=0;
	for(i=0;i<n;i++){
		for(j=0;j<m;j++)
			if(a[i]==b[j]) c[j]++;
	}
	return c;
}
/*
 * huffCode()
 * USAGE : rondomly generating codes of each char
 * c : modify c, c is the result of codes
 * n : charset size
 * m : length of codes of each sentence
 */
void huffCode(int *c,int n,int m){
	int i,j;
	long s,ran,tran;
	s=1;
	for(i=0;i<m;i++)
		s=s*n;
	if(s < 100){
		printf("Are you SB!\nThe m or n is too small or too big!\nChange them and try again!\n");
		exit(1);
	}
	srand(time(0));
	ran=rand()%s;	
	for(i=ran;i<(ran+100);i++){
		tran=i;
		for(j=0;j<m;j++){
			c[(i-ran)*m+j]=tran%n;
			tran=tran/n;
		}
	}
}